#pragma once

#include <atomic>
#include <memory>
#include "BiIterator.h"

template<typename T>
class ConcurrentBiLinkedList {
private:
    class Node {
    public:
        T dat;
        std::atomic<std::shared_ptr<Node>> next;
        std::atomic<std::shared_ptr<Node>> prev;

        Node() = default;

        explicit Node(T e) {
            dat = e;
        }
    };

    std::shared_ptr<Node> head;
    std::shared_ptr<Node> tail;

public:
    ConcurrentBiLinkedList() {
        this->head = std::make_shared<Node>();
        this->tail = std::make_shared<Node>();
        head->next = tail;
        tail->prev = head;
    }

    ~ConcurrentBiLinkedList() = default;

    void push_head(T e) {
        std::shared_ptr<Node> E = std::make_shared<Node>(e);
        while (true) {
            std::shared_ptr<Node> original_head = head->next.load();
            E->prev = this->head;
            E->next = original_head;
            if (head->next.compare_exchange_weak(original_head, E)) {
                original_head->prev = E;
                break;
            }
        }
    }

    void push_tail(T e) {
        std::shared_ptr<Node> E = std::make_shared<Node>(e);
        while (true) {
            std::shared_ptr<Node> original_tail = tail->prev.load();
            E->prev = original_tail;
            E->next = this->tail;
            if (tail->prev.compare_exchange_weak(original_tail, E)) {
                original_tail->next = E;
                break;
            }
        }
    }

    T get_head() {
        return head->next.load()->dat;
    }

    T get_tail() {
        return tail->prev.load()->dat;
    }

    class LinkedListBiIterator : public WritableBiIterator<T> {
    private:
        std::shared_ptr<Node> c;
        ConcurrentBiLinkedList& linkedList;

    public:
        explicit LinkedListBiIterator(ConcurrentBiLinkedList& linkedList_) : linkedList(linkedList_) {
            c = linkedList_.head;
        }

        LinkedListBiIterator(ConcurrentBiLinkedList& linkedList_, bool init_at_tail) : linkedList(linkedList_) {
            if (init_at_tail)
                c = linkedList_.tail;
            else
                c = linkedList_.head;
        }

        T current() const override {
            return c->dat;
        }

        bool MoveNext() override {
            if (c == linkedList.tail) return false;
            c = c->next.load();
            return true;
        }

        bool MovePrev() override {
            if (c == linkedList.head) return false;
            c = c->prev.load();
            return true;
        }

        void insertAfter(T e) override {
            std::shared_ptr<Node> E = std::make_shared<Node>(e);
            while (true) {
                std::shared_ptr<Node> original_next = c->next.load();
                E->next = original_next;
                E->prev = c;
                if (c->next.compare_exchange_weak(original_next, E)) {
                    original_next->prev = E;
                    break;
                }
            }
        }

        void insertBefore(T e) override {
            std::shared_ptr<Node> E = std::make_shared<Node>(e);
            while (true) {
                std::shared_ptr<Node> original_prev = c->prev.load();
                E->prev = original_prev;
                E->next = c;
                if (c->prev.compare_exchange_weak(original_prev, E)) {
                    original_prev->next = E;
                    break;
                }
            }
        }

        void remove() override {
            // 该无锁双向链表的实现是有漏洞的，处理删除有可能出现错误情况
            while (true) {
                std::shared_ptr<Node> pred = c->prev;
                std::shared_ptr<Node> pred_next = pred->next;
                if (c->prev.load()->next.compare_exchange_weak(c, c->next)) {
                    c->next.load()->prev = pred;
                    break;
                }
            }
        }
    };

    std::unique_ptr<WritableBiIterator<T>> getWritableIterator() {
        return std::make_unique<ConcurrentBiLinkedList::LinkedListBiIterator>(*this);
    }
};